package com.labuladong;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 *  斐波那契数
 */
public class FibonacciNumber {


    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
//        int fib = fib(45);
//        System.out.println(fib);

//        int[] temp=new int[122];
//        Arrays.fill(temp,0);
//        int fib = fib1(121,temp);
//        System.out.println(fib);

//        int fib = fib2(121);
//        System.out.println(fib);

        int fib = fib3(121);
        System.out.println(fib);

        long endTime = System.currentTimeMillis();
        System.out.println(endTime - startTime);
    }

    /**
     * 功能描述: 递归解法
     * @author huipanxing huipanxing@chinasofti.com
     * @date 2021/11/1 14:21
     * @param i
     * @return int
     */
    private static int fib(int i) {
        if (i == 0) {
            return 0;
        }
        if (i == 1) {
            return 1;
        }
        return fib(i - 1) + fib(i - 2);
    }

    /**
     * 功能描述: 动态规划解法(自顶向下)
     * @author huipanxing huipanxing@chinasofti.com
     * @date 2021/11/1 14:22
     * @param i
     * @return int
     */
    private static int fib1(int i, int[] temp) {
        if (temp[i] != 0) {
            return temp[i];
        }

        if (i == 0) {
            return 0;
        }
        if (i == 1) {
            return 1;
        }
        temp[i] = fib1(i - 1, temp) + fib1(i - 2, temp);
        return temp[i];
    }

    /**
     * 功能描述: dp数组解法（自底向上）
     * @author huipanxing huipanxing@chinasofti.com
     * @date 2021/11/1 14:22
     * @param i
     * @return int
     */
    private static int fib2(int i) {
        int[] temp = new int[i + 1];
        temp[0] = 0;
        temp[1] = 1;
        for (int n = 2; n <= i; n++) {
            temp[n] = temp[n - 1] + temp[n - 2];
        }
        return temp[i];
    }

    /**
     * 功能描述: dp数组解法（自底向上）空间复杂度O(1)
     * @author huipanxing huipanxing@chinasofti.com
     * @date 2021/11/1 14:22
     * @param i
     * @return int
     */
    private static int fib3(int i) {
        if (i==0){
            return 0;
        }
        if (i==1){
            return 1;
        }
        int prev=0;
        int curr=1;
        for (int n = 2; n <= i; n++) {
            int sum=prev+curr;
            prev=curr;
            curr=sum;
        }
        return curr;
    }
}
